package impl.sort;

import anaydis.sort.SorterType;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 04/10/2011
 * Time: 18:48:51
 * To change this template use File | Settings | File Templates.
 */
public class MergeBottomUpSorter extends AbstractSorter {
    public MergeBottomUpSorter() {
        super(SorterType.MERGE_BOTTOM_UP);
    }
    private <T> void merge(Comparator<T> c, List<T> list, int l, int m, int r) {
        if(l<r){
            List<T> aux = new ArrayList<T>();
            for(int i=l; i<=m; i++){
                aux.add(list.get(i));
            }
            for(int j=m+1; j<=r; j++){
                aux.add(list.get(r-j+m+1));
            }
            int i = 0;
            int j = r-l;
            for(int k=l; k<=r; k++){
                if(!greater(c, aux, i, j)){
                    list.set(k, aux.get(i));
                    i++;
                }else{
                    list.set(k, aux.get(j));
                    j--;
                }
            }
        }
    }
    public <T> void sort(Comparator<T> c, List<T> list) {
        int n = list.size();
        int i;
        for(i=2; i<n; i*=2){
            for(int j=0; j<n; j+=i){
                if(j!=n-1){
                    int m;
                    if((j+(i/2)-1)<n-1){
                        m = j+(i/2)-1;
                    }else{
                        m = j+((n-j)/2);
                    }
                    merge(c, list, j, m, Math.min(j+i-1, n-1));
                }
            }
        }
        merge(c, list, 0, (i/2)-1, n-1);
    }
}
